// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_HEAP_MARK_COMPACT_H_
#define V8_HEAP_MARK_COMPACT_H_

#include <atomic>
#include <vector>

#include "src/heap/concurrent-marking.h"
#include "src/heap/marking.h"
#include "src/heap/objects-visiting.h"
#include "src/heap/spaces.h"
#include "src/heap/sweeper.h"
#include "src/heap/worklist.h"
#include "src/objects/heap-object.h" // For Worklist<HeapObject, ...>
#include "src/objects/js-weak-refs.h" // For Worklist<WeakCell, ...>

namespace v8 {
namespace internal {

    // Forward declarations.
    class EvacuationJobTraits;
    class HeapObjectVisitor;
    class ItemParallelJob;
    class MigrationObserver;
    class RecordMigratedSlotVisitor;
    class UpdatingItem;
    class YoungGenerationMarkingVisitor;

    template <typename ConcreteState, AccessMode access_mode>
    class MarkingStateBase {
    public:
        V8_INLINE MarkBit MarkBitFrom(HeapObject obj)
        {
            return MarkBitFrom(MemoryChunk::FromHeapObject(obj), obj->ptr());
        }

        // {addr} may be tagged or aligned.
        V8_INLINE MarkBit MarkBitFrom(MemoryChunk* p, Address addr)
        {
            return static_cast<ConcreteState*>(this)->bitmap(p)->MarkBitFromIndex(
                p->AddressToMarkbitIndex(addr));
        }

        Marking::ObjectColor Color(HeapObject obj)
        {
            return Marking::Color(MarkBitFrom(obj));
        }

        V8_INLINE bool IsImpossible(HeapObject obj)
        {
            return Marking::IsImpossible<access_mode>(MarkBitFrom(obj));
        }

        V8_INLINE bool IsBlack(HeapObject obj)
        {
            return Marking::IsBlack<access_mode>(MarkBitFrom(obj));
        }

        V8_INLINE bool IsWhite(HeapObject obj)
        {
            return Marking::IsWhite<access_mode>(MarkBitFrom(obj));
        }

        V8_INLINE bool IsGrey(HeapObject obj)
        {
            return Marking::IsGrey<access_mode>(MarkBitFrom(obj));
        }

        V8_INLINE bool IsBlackOrGrey(HeapObject obj)
        {
            return Marking::IsBlackOrGrey<access_mode>(MarkBitFrom(obj));
        }

        V8_INLINE bool WhiteToGrey(HeapObject obj);
        V8_INLINE bool WhiteToBlack(HeapObject obj);
        V8_INLINE bool GreyToBlack(HeapObject obj);

        void ClearLiveness(MemoryChunk* chunk)
        {
            static_cast<ConcreteState*>(this)->bitmap(chunk)->Clear();
            static_cast<ConcreteState*>(this)->SetLiveBytes(chunk, 0);
        }
    };

    class MarkBitCellIterator {
    public:
        MarkBitCellIterator(MemoryChunk* chunk, Bitmap* bitmap)
            : chunk_(chunk)
        {
            last_cell_index_ = Bitmap::IndexToCell(chunk_->AddressToMarkbitIndex(chunk_->area_end()));
            cell_base_ = chunk_->address();
            cell_index_ = Bitmap::IndexToCell(chunk_->AddressToMarkbitIndex(cell_base_));
            cells_ = bitmap->cells();
        }

        inline bool Done() { return cell_index_ >= last_cell_index_; }

        inline bool HasNext() { return cell_index_ < last_cell_index_ - 1; }

        inline MarkBit::CellType* CurrentCell()
        {
            DCHECK_EQ(cell_index_, Bitmap::IndexToCell(Bitmap::CellAlignIndex(chunk_->AddressToMarkbitIndex(cell_base_))));
            return &cells_[cell_index_];
        }

        inline Address CurrentCellBase()
        {
            DCHECK_EQ(cell_index_, Bitmap::IndexToCell(Bitmap::CellAlignIndex(chunk_->AddressToMarkbitIndex(cell_base_))));
            return cell_base_;
        }

        V8_WARN_UNUSED_RESULT inline bool Advance()
        {
            cell_base_ += Bitmap::kBitsPerCell * kTaggedSize;
            return ++cell_index_ != last_cell_index_;
        }

        inline bool Advance(unsigned int new_cell_index)
        {
            if (new_cell_index != cell_index_) {
                DCHECK_GT(new_cell_index, cell_index_);
                DCHECK_LE(new_cell_index, last_cell_index_);
                unsigned int diff = new_cell_index - cell_index_;
                cell_index_ = new_cell_index;
                cell_base_ += diff * (Bitmap::kBitsPerCell * kTaggedSize);
                return true;
            }
            return false;
        }

        // Return the next mark bit cell. If there is no next it returns 0;
        inline MarkBit::CellType PeekNext()
        {
            if (HasNext()) {
                return cells_[cell_index_ + 1];
            }
            return 0;
        }

    private:
        MemoryChunk* chunk_;
        MarkBit::CellType* cells_;
        unsigned int last_cell_index_;
        unsigned int cell_index_;
        Address cell_base_;
    };

    enum LiveObjectIterationMode {
        kBlackObjects,
        kGreyObjects,
        kAllLiveObjects
    };

    template <LiveObjectIterationMode mode>
    class LiveObjectRange {
    public:
        class iterator {
        public:
            using value_type = std::pair<HeapObject, int /* size */>;
            using pointer = const value_type*;
            using reference = const value_type&;
            using iterator_category = std::forward_iterator_tag;

            inline iterator(MemoryChunk* chunk, Bitmap* bitmap, Address start);

            inline iterator& operator++();
            inline iterator operator++(int);

            bool operator==(iterator other) const
            {
                return current_object_ == other.current_object_;
            }

            bool operator!=(iterator other) const { return !(*this == other); }

            value_type operator*()
            {
                return std::make_pair(current_object_, current_size_);
            }

        private:
            inline void AdvanceToNextValidObject();

            MemoryChunk* const chunk_;
            Map const one_word_filler_map_;
            Map const two_word_filler_map_;
            Map const free_space_map_;
            MarkBitCellIterator it_;
            Address cell_base_;
            MarkBit::CellType current_cell_;
            HeapObject current_object_;
            int current_size_;
        };

        LiveObjectRange(MemoryChunk* chunk, Bitmap* bitmap)
            : chunk_(chunk)
            , bitmap_(bitmap)
            , start_(chunk_->area_start())
            , end_(chunk->area_end())
        {
            DCHECK(!chunk->IsLargePage());
        }

        inline iterator begin();
        inline iterator end();

    private:
        MemoryChunk* const chunk_;
        Bitmap* bitmap_;
        Address start_;
        Address end_;
    };

    class LiveObjectVisitor : AllStatic {
    public:
        enum IterationMode {
            kKeepMarking,
            kClearMarkbits,
        };

        // Visits black objects on a MemoryChunk until the Visitor returns |false| for
        // an object. If IterationMode::kClearMarkbits is passed the markbits and
        // slots for visited objects are cleared for each successfully visited object.
        template <class Visitor, typename MarkingState>
        static bool VisitBlackObjects(MemoryChunk* chunk, MarkingState* state,
            Visitor* visitor, IterationMode iteration_mode,
            HeapObject* failed_object);

        // Visits black objects on a MemoryChunk. The visitor is not allowed to fail
        // visitation for an object.
        template <class Visitor, typename MarkingState>
        static void VisitBlackObjectsNoFail(MemoryChunk* chunk, MarkingState* state,
            Visitor* visitor,
            IterationMode iteration_mode);

        // Visits black objects on a MemoryChunk. The visitor is not allowed to fail
        // visitation for an object.
        template <class Visitor, typename MarkingState>
        static void VisitGreyObjectsNoFail(MemoryChunk* chunk, MarkingState* state,
            Visitor* visitor,
            IterationMode iteration_mode);

        template <typename MarkingState>
        static void RecomputeLiveBytes(MemoryChunk* chunk, MarkingState* state);
    };

    enum PageEvacuationMode { NEW_TO_NEW,
        NEW_TO_OLD };
    enum MarkingTreatmentMode { KEEP,
        CLEAR };
    enum class RememberedSetUpdatingMode { ALL,
        OLD_TO_NEW_ONLY };

    // Base class for minor and full MC collectors.
    class MarkCompactCollectorBase {
    public:
        static const int kMainThread = 0;

        virtual ~MarkCompactCollectorBase() = default;

        virtual void SetUp() = 0;
        virtual void TearDown() = 0;
        virtual void CollectGarbage() = 0;

        inline Heap* heap() const { return heap_; }
        inline Isolate* isolate();

    protected:
        explicit MarkCompactCollectorBase(Heap* heap)
            : heap_(heap)
            , old_to_new_slots_(0)
        {
        }

        // Marking operations for objects reachable from roots.
        virtual void MarkLiveObjects() = 0;
        // Mark objects reachable (transitively) from objects in the marking
        // work list.
        virtual void ProcessMarkingWorklist() = 0;
        // Clear non-live references held in side data structures.
        virtual void ClearNonLiveReferences() = 0;
        virtual void EvacuatePrologue() = 0;
        virtual void EvacuateEpilogue() = 0;
        virtual void Evacuate() = 0;
        virtual void EvacuatePagesInParallel() = 0;
        virtual void UpdatePointersAfterEvacuation() = 0;
        virtual UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk,
            Address start,
            Address end)
            = 0;
        virtual UpdatingItem* CreateRememberedSetUpdatingItem(
            MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode)
            = 0;

        template <class Evacuator, class Collector>
        void CreateAndExecuteEvacuationTasks(Collector* collector,
            ItemParallelJob* job,
            MigrationObserver* migration_observer,
            const intptr_t live_bytes);

        // Returns whether this page should be moved according to heuristics.
        bool ShouldMovePage(Page* p, intptr_t live_bytes);

        int CollectToSpaceUpdatingItems(ItemParallelJob* job);
        template <typename IterateableSpace>
        int CollectRememberedSetUpdatingItems(ItemParallelJob* job,
            IterateableSpace* space,
            RememberedSetUpdatingMode mode);

        int NumberOfParallelCompactionTasks(int pages);
        int NumberOfParallelPointerUpdateTasks(int pages, int slots);
        int NumberOfParallelToSpacePointerUpdateTasks(int pages);

        Heap* heap_;
        // Number of old to new slots. Should be computed during MarkLiveObjects.
        // -1 indicates that the value couldn't be computed.
        int old_to_new_slots_;
    };

    class MinorMarkingState final
        : public MarkingStateBase<MinorMarkingState, AccessMode::ATOMIC> {
    public:
        ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const
        {
            return chunk->young_generation_bitmap<AccessMode::ATOMIC>();
        }

        void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by)
        {
            chunk->young_generation_live_byte_count_ += by;
        }

        intptr_t live_bytes(MemoryChunk* chunk) const
        {
            return chunk->young_generation_live_byte_count_;
        }

        void SetLiveBytes(MemoryChunk* chunk, intptr_t value)
        {
            chunk->young_generation_live_byte_count_ = value;
        }
    };

    class MinorNonAtomicMarkingState final
        : public MarkingStateBase<MinorNonAtomicMarkingState,
              AccessMode::NON_ATOMIC> {
    public:
        ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap(
            const MemoryChunk* chunk) const
        {
            return chunk->young_generation_bitmap<AccessMode::NON_ATOMIC>();
        }

        void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by)
        {
            chunk->young_generation_live_byte_count_.fetch_add(
                by, std::memory_order_relaxed);
        }

        intptr_t live_bytes(MemoryChunk* chunk) const
        {
            return chunk->young_generation_live_byte_count_.load(
                std::memory_order_relaxed);
        }

        void SetLiveBytes(MemoryChunk* chunk, intptr_t value)
        {
            chunk->young_generation_live_byte_count_.store(value,
                std::memory_order_relaxed);
        }
    };

    // This marking state is used when concurrent marking is running.
    class IncrementalMarkingState final
        : public MarkingStateBase<IncrementalMarkingState, AccessMode::ATOMIC> {
    public:
        ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const
        {
            DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - reinterpret_cast<intptr_t>(chunk),
                MemoryChunk::kMarkBitmapOffset);
            return chunk->marking_bitmap<AccessMode::ATOMIC>();
        }

        // Concurrent marking uses local live bytes so we may do these accesses
        // non-atomically.
        void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by)
        {
            chunk->live_byte_count_ += by;
        }

        intptr_t live_bytes(MemoryChunk* chunk) const
        {
            return chunk->live_byte_count_;
        }

        void SetLiveBytes(MemoryChunk* chunk, intptr_t value)
        {
            chunk->live_byte_count_ = value;
        }
    };

    class MajorAtomicMarkingState final
        : public MarkingStateBase<MajorAtomicMarkingState, AccessMode::ATOMIC> {
    public:
        ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const
        {
            DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - reinterpret_cast<intptr_t>(chunk),
                MemoryChunk::kMarkBitmapOffset);
            return chunk->marking_bitmap<AccessMode::ATOMIC>();
        }

        void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by)
        {
            std::atomic_fetch_add(
                reinterpret_cast<std::atomic<intptr_t>*>(&chunk->live_byte_count_), by);
        }
    };

    class MajorNonAtomicMarkingState final
        : public MarkingStateBase<MajorNonAtomicMarkingState,
              AccessMode::NON_ATOMIC> {
    public:
        ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap(
            const MemoryChunk* chunk) const
        {
            DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - reinterpret_cast<intptr_t>(chunk),
                MemoryChunk::kMarkBitmapOffset);
            return chunk->marking_bitmap<AccessMode::NON_ATOMIC>();
        }

        void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by)
        {
            chunk->live_byte_count_ += by;
        }

        intptr_t live_bytes(MemoryChunk* chunk) const
        {
            return chunk->live_byte_count_;
        }

        void SetLiveBytes(MemoryChunk* chunk, intptr_t value)
        {
            chunk->live_byte_count_ = value;
        }
    };

    struct Ephemeron {
        HeapObject key;
        HeapObject value;
    };

    using EphemeronWorklist = Worklist<Ephemeron, 64>;

    // Weak objects encountered during marking.
    struct WeakObjects {
        Worklist<TransitionArray, 64> transition_arrays;

        // Keep track of all EphemeronHashTables in the heap to process
        // them in the atomic pause.
        Worklist<EphemeronHashTable, 64> ephemeron_hash_tables;

        // Keep track of all ephemerons for concurrent marking tasks. Only store
        // ephemerons in these Worklists if both key and value are unreachable at the
        // moment.
        //
        // MarkCompactCollector::ProcessEphemeronsUntilFixpoint drains and fills these
        // worklists.
        //
        // current_ephemerons is used as draining worklist in the current fixpoint
        // iteration.
        EphemeronWorklist current_ephemerons;

        // Stores ephemerons to visit in the next fixpoint iteration.
        EphemeronWorklist next_ephemerons;

        // When draining the marking worklist new discovered ephemerons are pushed
        // into this worklist.
        EphemeronWorklist discovered_ephemerons;

        // TODO(marja): For old space, we only need the slot, not the host
        // object. Optimize this by adding a different storage for old space.
        Worklist<std::pair<HeapObject, HeapObjectSlot>, 64> weak_references;
        Worklist<std::pair<HeapObject, Code>, 64> weak_objects_in_code;

        Worklist<JSWeakRef, 64> js_weak_refs;
        Worklist<WeakCell, 64> weak_cells;

        Worklist<SharedFunctionInfo, 64> bytecode_flushing_candidates;
        Worklist<JSFunction, 64> flushed_js_functions;
    };

    struct EphemeronMarking {
        std::vector<HeapObject> newly_discovered;
        bool newly_discovered_overflowed;
        size_t newly_discovered_limit;
    };

    // Collector for young and old generation.
    class MarkCompactCollector final : public MarkCompactCollectorBase {
    public:
#ifdef V8_CONCURRENT_MARKING
        using MarkingState = IncrementalMarkingState;
#else
        using MarkingState = MajorNonAtomicMarkingState;
#endif // V8_CONCURRENT_MARKING

        using NonAtomicMarkingState = MajorNonAtomicMarkingState;

        // Wrapper for the shared worklist.
        class MarkingWorklist {
        public:
            using ConcurrentMarkingWorklist = Worklist<HeapObject, 64>;
            using EmbedderTracingWorklist = Worklist<HeapObject, 16>;

            // The heap parameter is not used but needed to match the sequential case.
            explicit MarkingWorklist(Heap* heap) { }

            void Push(HeapObject object)
            {
                bool success = shared_.Push(kMainThread, object);
                USE(success);
                DCHECK(success);
            }

            HeapObject Pop()
            {
                HeapObject result;
                if (shared_.Pop(kMainThread, &result))
                    return result;
#ifdef V8_CONCURRENT_MARKING
                // The expectation is that this work list is empty almost all the time
                // and we can thus avoid the emptiness checks by putting it last.
                if (on_hold_.Pop(kMainThread, &result))
                    return result;
#endif
                return HeapObject();
            }

            void Clear()
            {
                shared_.Clear();
                on_hold_.Clear();
                embedder_.Clear();
            }

            bool IsEmpty()
            {
                return shared_.IsLocalEmpty(kMainThread) && on_hold_.IsLocalEmpty(kMainThread) && shared_.IsGlobalPoolEmpty() && on_hold_.IsGlobalPoolEmpty();
            }

            bool IsEmbedderEmpty()
            {
                return embedder_.IsLocalEmpty(kMainThread) && embedder_.IsGlobalPoolEmpty();
            }

            int Size()
            {
                return static_cast<int>(shared_.LocalSize(kMainThread) + on_hold_.LocalSize(kMainThread));
            }

            // Calls the specified callback on each element of the deques and replaces
            // the element with the result of the callback. If the callback returns
            // nullptr then the element is removed from the deque.
            // The callback must accept HeapObject and return HeapObject.
            template <typename Callback>
            void Update(Callback callback)
            {
                shared_.Update(callback);
                on_hold_.Update(callback);
                embedder_.Update(callback);
            }

            void ShareWorkIfGlobalPoolIsEmpty()
            {
                if (!shared_.IsLocalEmpty(kMainThread) && shared_.IsGlobalPoolEmpty()) {
                    shared_.FlushToGlobal(kMainThread);
                }
            }

            ConcurrentMarkingWorklist* shared() { return &shared_; }
            ConcurrentMarkingWorklist* on_hold() { return &on_hold_; }
            EmbedderTracingWorklist* embedder() { return &embedder_; }

            void Print()
            {
                PrintWorklist("shared", &shared_);
                PrintWorklist("on_hold", &on_hold_);
            }

        private:
            // Prints the stats about the global pool of the worklist.
            void PrintWorklist(const char* worklist_name,
                ConcurrentMarkingWorklist* worklist);

            // Worklist used for most objects.
            ConcurrentMarkingWorklist shared_;

            // Concurrent marking uses this worklist to bail out of marking objects
            // in new space's linear allocation area. Used to avoid black allocation
            // for new space. This allow the compiler to remove write barriers
            // for freshly allocatd objects.
            ConcurrentMarkingWorklist on_hold_;

            // Worklist for objects that potentially require embedder tracing, i.e.,
            // these objects need to be handed over to the embedder to find the full
            // transitive closure.
            EmbedderTracingWorklist embedder_;
        };

        class RootMarkingVisitor;
        class CustomRootBodyMarkingVisitor;

        enum IterationMode {
            kKeepMarking,
            kClearMarkbits,
        };

        MarkingState* marking_state() { return &marking_state_; }

        NonAtomicMarkingState* non_atomic_marking_state()
        {
            return &non_atomic_marking_state_;
        }

        void SetUp() override;
        void TearDown() override;
        // Performs a global garbage collection.
        void CollectGarbage() override;

        void CollectEvacuationCandidates(PagedSpace* space);

        void AddEvacuationCandidate(Page* p);

        // Prepares for GC by resetting relocation info in old and map spaces and
        // choosing spaces to compact.
        void Prepare();

        // Stop concurrent marking (either by preempting it right away or waiting for
        // it to complete as requested by |stop_request|).
        void FinishConcurrentMarking(ConcurrentMarking::StopRequest stop_request);

        bool StartCompaction();

        void AbortCompaction();

        static inline bool IsOnEvacuationCandidate(Object obj)
        {
            return Page::FromAddress(obj->ptr())->IsEvacuationCandidate();
        }

        static bool IsOnEvacuationCandidate(MaybeObject obj);

        struct RecordRelocSlotInfo {
            MemoryChunk* memory_chunk;
            SlotType slot_type;
            bool should_record;
            uint32_t offset;
        };
        static RecordRelocSlotInfo PrepareRecordRelocSlot(Code host, RelocInfo* rinfo,
            HeapObject target);
        static void RecordRelocSlot(Code host, RelocInfo* rinfo, HeapObject target);
        V8_INLINE static void RecordSlot(HeapObject object, ObjectSlot slot,
            HeapObject target);
        V8_INLINE static void RecordSlot(HeapObject object, HeapObjectSlot slot,
            HeapObject target);
        void RecordLiveSlotsOnPage(Page* page);

        void UpdateSlots(SlotsBuffer* buffer);
        void UpdateSlotsRecordedIn(SlotsBuffer* buffer);

        bool is_compacting() const { return compacting_; }

        // Ensures that sweeping is finished.
        //
        // Note: Can only be called safely from main thread.
        V8_EXPORT_PRIVATE void EnsureSweepingCompleted();

        // Checks if sweeping is in progress right now on any space.
        bool sweeping_in_progress() const { return sweeper_->sweeping_in_progress(); }

        void set_evacuation(bool evacuation) { evacuation_ = evacuation; }

        bool evacuation() const { return evacuation_; }

        MarkingWorklist* marking_worklist() { return &marking_worklist_; }

        WeakObjects* weak_objects() { return &weak_objects_; }

        inline void AddTransitionArray(TransitionArray array);

        void AddEphemeronHashTable(EphemeronHashTable table)
        {
            weak_objects_.ephemeron_hash_tables.Push(kMainThread, table);
        }

        void AddEphemeron(HeapObject key, HeapObject value)
        {
            weak_objects_.discovered_ephemerons.Push(kMainThread,
                Ephemeron { key, value });
        }

        void AddWeakReference(HeapObject host, HeapObjectSlot slot)
        {
            weak_objects_.weak_references.Push(kMainThread, std::make_pair(host, slot));
        }

        void AddWeakObjectInCode(HeapObject object, Code code)
        {
            weak_objects_.weak_objects_in_code.Push(kMainThread,
                std::make_pair(object, code));
        }

        void AddWeakRef(JSWeakRef weak_ref)
        {
            weak_objects_.js_weak_refs.Push(kMainThread, weak_ref);
        }

        void AddWeakCell(WeakCell weak_cell)
        {
            weak_objects_.weak_cells.Push(kMainThread, weak_cell);
        }

        inline void AddBytecodeFlushingCandidate(SharedFunctionInfo flush_candidate);
        inline void AddFlushedJSFunction(JSFunction flushed_function);

        void AddNewlyDiscovered(HeapObject object)
        {
            if (ephemeron_marking_.newly_discovered_overflowed)
                return;

            if (ephemeron_marking_.newly_discovered.size() < ephemeron_marking_.newly_discovered_limit) {
                ephemeron_marking_.newly_discovered.push_back(object);
            } else {
                ephemeron_marking_.newly_discovered_overflowed = true;
            }
        }

        void ResetNewlyDiscovered()
        {
            ephemeron_marking_.newly_discovered_overflowed = false;
            ephemeron_marking_.newly_discovered.clear();
        }

        Sweeper* sweeper() { return sweeper_; }

#ifdef DEBUG
        // Checks whether performing mark-compact collection.
        bool in_use() { return state_ > PREPARE_GC; }
        bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; }
#endif

        void VerifyMarking();
#ifdef VERIFY_HEAP
        void VerifyValidStoreAndSlotsBufferEntries();
        void VerifyMarkbitsAreClean();
        void VerifyMarkbitsAreDirty(PagedSpace* space);
        void VerifyMarkbitsAreClean(PagedSpace* space);
        void VerifyMarkbitsAreClean(NewSpace* space);
        void VerifyMarkbitsAreClean(LargeObjectSpace* space);
#endif

        unsigned epoch() const
        {
            return epoch_;
        }

        explicit MarkCompactCollector(Heap* heap);
        ~MarkCompactCollector() override;

        // Used by wrapper tracing.
        V8_INLINE void MarkExternallyReferencedObject(HeapObject obj);

    private:
        void ComputeEvacuationHeuristics(size_t area_size,
            int* target_fragmentation_percent,
            size_t* max_evacuated_bytes);

        void RecordObjectStats();

        // Finishes GC, performs heap verification if enabled.
        void Finish();

        void MarkLiveObjects() override;

        // Marks the object black and adds it to the marking work list.
        // This is for non-incremental marking only.
        V8_INLINE void MarkObject(HeapObject host, HeapObject obj);

        // Marks the object black and adds it to the marking work list.
        // This is for non-incremental marking only.
        V8_INLINE void MarkRootObject(Root root, HeapObject obj);

        // Mark the heap roots and all objects reachable from them.
        void MarkRoots(RootVisitor* root_visitor,
            ObjectVisitor* custom_root_body_visitor);

        // Mark the string table specially.  References to internalized strings from
        // the string table are weak.
        void MarkStringTable(ObjectVisitor* visitor);

        // Marks object reachable from harmony weak maps and wrapper tracing.
        void ProcessEphemeronMarking();

        // If the call-site of the top optimized code was not prepared for
        // deoptimization, then treat embedded pointers in the code as strong as
        // otherwise they can die and try to deoptimize the underlying code.
        void ProcessTopOptimizedFrame(ObjectVisitor* visitor);

        // Drains the main thread marking work list. Will mark all pending objects
        // if no concurrent threads are running.
        void ProcessMarkingWorklist() override;

        enum class MarkingWorklistProcessingMode {
            kDefault,
            kTrackNewlyDiscoveredObjects
        };

        template <MarkingWorklistProcessingMode mode>
        void ProcessMarkingWorklistInternal();

        // Implements ephemeron semantics: Marks value if key is already reachable.
        // Returns true if value was actually marked.
        bool ProcessEphemeron(HeapObject key, HeapObject value);

        // Marks ephemerons and drains marking worklist iteratively
        // until a fixpoint is reached.
        void ProcessEphemeronsUntilFixpoint();

        // Drains ephemeron and marking worklists. Single iteration of the
        // fixpoint iteration.
        bool ProcessEphemerons();

        // Mark ephemerons and drain marking worklist with a linear algorithm.
        // Only used if fixpoint iteration doesn't finish within a few iterations.
        void ProcessEphemeronsLinear();

        // Perform Wrapper Tracing if in use.
        void PerformWrapperTracing();

        // Callback function for telling whether the object *p is an unmarked
        // heap object.
        static bool IsUnmarkedHeapObject(Heap* heap, FullObjectSlot p);

        // Clear non-live references in weak cells, transition and descriptor arrays,
        // and deoptimize dependent code of non-live maps.
        void ClearNonLiveReferences() override;
        void MarkDependentCodeForDeoptimization();
        // Checks if the given weak cell is a simple transition from the parent map
        // of the given dead target. If so it clears the transition and trims
        // the descriptor array of the parent if needed.
        void ClearPotentialSimpleMapTransition(Map dead_target);
        void ClearPotentialSimpleMapTransition(Map map, Map dead_target);

        // Flushes a weakly held bytecode array from a shared function info.
        void FlushBytecodeFromSFI(SharedFunctionInfo shared_info);

        // Clears bytecode arrays that have not been executed for multiple
        // collections.
        void ClearOldBytecodeCandidates();

        // Resets any JSFunctions which have had their bytecode flushed.
        void ClearFlushedJsFunctions();

        // Compact every array in the global list of transition arrays and
        // trim the corresponding descriptor array if a transition target is non-live.
        void ClearFullMapTransitions();
        void TrimDescriptorArray(Map map, DescriptorArray descriptors);
        void TrimEnumCache(Map map, DescriptorArray descriptors);
        bool CompactTransitionArray(Map map, TransitionArray transitions,
            DescriptorArray descriptors);

        // After all reachable objects have been marked those weak map entries
        // with an unreachable key are removed from all encountered weak maps.
        // The linked list of all encountered weak maps is destroyed.
        void ClearWeakCollections();

        // Goes through the list of encountered weak references and clears those with
        // dead values. If the value is a dead map and the parent map transitions to
        // the dead map via weak cell, then this function also clears the map
        // transition.
        void ClearWeakReferences();

        // Goes through the list of encountered JSWeakRefs and WeakCells and clears
        // those with dead values.
        void ClearJSWeakRefs();

        void AbortWeakObjects();

        // Starts sweeping of spaces by contributing on the main thread and setting
        // up other pages for sweeping. Does not start sweeper tasks.
        void StartSweepSpaces();
        void StartSweepSpace(PagedSpace* space);

        void EvacuatePrologue() override;
        void EvacuateEpilogue() override;
        void Evacuate() override;
        void EvacuatePagesInParallel() override;
        void UpdatePointersAfterEvacuation() override;

        UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk, Address start,
            Address end) override;
        UpdatingItem* CreateRememberedSetUpdatingItem(
            MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) override;

        int CollectNewSpaceArrayBufferTrackerItems(ItemParallelJob* job);
        int CollectOldSpaceArrayBufferTrackerItems(ItemParallelJob* job);

        void ReleaseEvacuationCandidates();
        void PostProcessEvacuationCandidates();
        void ReportAbortedEvacuationCandidate(HeapObject failed_object,
            MemoryChunk* chunk);

        static const int kEphemeronChunkSize = 8 * KB;

        int NumberOfParallelEphemeronVisitingTasks(size_t elements);

        void RightTrimDescriptorArray(DescriptorArray array, int descriptors_to_trim);

        base::Mutex mutex_;
        base::Semaphore page_parallel_job_semaphore_;

#ifdef DEBUG
        enum CollectorState {
            IDLE,
            PREPARE_GC,
            MARK_LIVE_OBJECTS,
            SWEEP_SPACES,
            ENCODE_FORWARDING_ADDRESSES,
            UPDATE_POINTERS,
            RELOCATE_OBJECTS
        };

        // The current stage of the collector.
        CollectorState state_;
#endif

        bool was_marked_incrementally_;

        bool evacuation_;

        // True if we are collecting slots to perform evacuation from evacuation
        // candidates.
        bool compacting_;

        bool black_allocation_;

        bool have_code_to_deoptimize_;

        MarkingWorklist marking_worklist_;
        WeakObjects weak_objects_;
        EphemeronMarking ephemeron_marking_;

        // Candidates for pages that should be evacuated.
        std::vector<Page*> evacuation_candidates_;
        // Pages that are actually processed during evacuation.
        std::vector<Page*> old_space_evacuation_pages_;
        std::vector<Page*> new_space_evacuation_pages_;
        std::vector<std::pair<HeapObject, Page*>> aborted_evacuation_candidates_;

        Sweeper* sweeper_;

        MarkingState marking_state_;
        NonAtomicMarkingState non_atomic_marking_state_;

        // Counts the number of mark-compact collections. This is used for marking
        // descriptor arrays. See NumberOfMarkedDescriptors. Only lower two bits are
        // used, so it is okay if this counter overflows and wraps around.
        unsigned epoch_ = 0;

        friend class FullEvacuator;
        friend class RecordMigratedSlotVisitor;
    };

    template <FixedArrayVisitationMode fixed_array_mode,
        TraceRetainingPathMode retaining_path_mode, typename MarkingState>
    class MarkingVisitor final
        : public HeapVisitor<
              int,
              MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>> {
    public:
        using Parent = HeapVisitor<
            int, MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>>;

        V8_INLINE MarkingVisitor(MarkCompactCollector* collector,
            MarkingState* marking_state);

        V8_INLINE bool ShouldVisitMapPointer() { return false; }

        V8_INLINE int VisitBytecodeArray(Map map, BytecodeArray object);
        V8_INLINE int VisitDescriptorArray(Map map, DescriptorArray object);
        V8_INLINE int VisitEphemeronHashTable(Map map, EphemeronHashTable object);
        V8_INLINE int VisitFixedArray(Map map, FixedArray object);
        V8_INLINE int VisitJSApiObject(Map map, JSObject object);
        V8_INLINE int VisitJSArrayBuffer(Map map, JSArrayBuffer object);
        V8_INLINE int VisitJSFunction(Map map, JSFunction object);
        V8_INLINE int VisitJSDataView(Map map, JSDataView object);
        V8_INLINE int VisitJSTypedArray(Map map, JSTypedArray object);
        V8_INLINE int VisitMap(Map map, Map object);
        V8_INLINE int VisitSharedFunctionInfo(Map map, SharedFunctionInfo object);
        V8_INLINE int VisitTransitionArray(Map map, TransitionArray object);
        V8_INLINE int VisitWeakCell(Map map, WeakCell object);
        V8_INLINE int VisitJSWeakRef(Map map, JSWeakRef object);

        // ObjectVisitor implementation.
        V8_INLINE void VisitPointer(HeapObject host, ObjectSlot p) final
        {
            VisitPointerImpl(host, p);
        }
        V8_INLINE void VisitPointer(HeapObject host, MaybeObjectSlot p) final
        {
            VisitPointerImpl(host, p);
        }
        V8_INLINE void VisitPointers(HeapObject host, ObjectSlot start,
            ObjectSlot end) final
        {
            VisitPointersImpl(host, start, end);
        }
        V8_INLINE void VisitPointers(HeapObject host, MaybeObjectSlot start,
            MaybeObjectSlot end) final
        {
            VisitPointersImpl(host, start, end);
        }
        V8_INLINE void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final;
        V8_INLINE void VisitCodeTarget(Code host, RelocInfo* rinfo) final;

        // Weak list pointers should be ignored during marking. The lists are
        // reconstructed after GC.
        void VisitCustomWeakPointers(HeapObject host, ObjectSlot start,
            ObjectSlot end) final { }

        V8_INLINE void VisitDescriptors(DescriptorArray descriptors,
            int number_of_own_descriptors);
        // Marks the descriptor array black without pushing it on the marking work
        // list and visits its header.
        V8_INLINE void MarkDescriptorArrayBlack(HeapObject host,
            DescriptorArray descriptors);

    private:
        // Granularity in which FixedArrays are scanned if |fixed_array_mode|
        // is true.
        static const int kProgressBarScanningChunk = 32 * KB;

        template <typename TSlot>
        V8_INLINE void VisitPointerImpl(HeapObject host, TSlot p);

        template <typename TSlot>
        V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end);

        V8_INLINE int VisitFixedArrayIncremental(Map map, FixedArray object);

        template <typename T>
        V8_INLINE int VisitEmbedderTracingSubclass(Map map, T object);

        // Marks the object grey and pushes it on the marking work list.
        V8_INLINE void MarkObject(HeapObject host, HeapObject obj);

        MarkingState* marking_state() { return marking_state_; }

        MarkCompactCollector::MarkingWorklist* marking_worklist() const
        {
            return collector_->marking_worklist();
        }

        Heap* const heap_;
        MarkCompactCollector* const collector_;
        MarkingState* const marking_state_;
        const unsigned mark_compact_epoch_;
    };

    class EvacuationScope {
    public:
        explicit EvacuationScope(MarkCompactCollector* collector)
            : collector_(collector)
        {
            collector_->set_evacuation(true);
        }

        ~EvacuationScope() { collector_->set_evacuation(false); }

    private:
        MarkCompactCollector* collector_;
    };

#ifdef ENABLE_MINOR_MC

    // Collector for young-generation only.
    class MinorMarkCompactCollector final : public MarkCompactCollectorBase {
    public:
        using MarkingState = MinorMarkingState;
        using NonAtomicMarkingState = MinorNonAtomicMarkingState;

        explicit MinorMarkCompactCollector(Heap* heap);
        ~MinorMarkCompactCollector() override;

        MarkingState* marking_state() { return &marking_state_; }

        NonAtomicMarkingState* non_atomic_marking_state()
        {
            return &non_atomic_marking_state_;
        }

        void SetUp() override;
        void TearDown() override;
        void CollectGarbage() override;

        void MakeIterable(Page* page, MarkingTreatmentMode marking_mode,
            FreeSpaceTreatmentMode free_space_mode);
        void CleanupSweepToIteratePages();

    private:
        using MarkingWorklist = Worklist<HeapObject, 64 /* segment size */>;
        class RootMarkingVisitor;

        static const int kNumMarkers = 8;
        static const int kMainMarker = 0;

        inline MarkingWorklist* worklist() { return worklist_; }

        inline YoungGenerationMarkingVisitor* main_marking_visitor()
        {
            return main_marking_visitor_;
        }

        void MarkLiveObjects() override;
        void MarkRootSetInParallel(RootMarkingVisitor* root_visitor);
        V8_INLINE void MarkRootObject(HeapObject obj);
        void ProcessMarkingWorklist() override;
        void ClearNonLiveReferences() override;

        void EvacuatePrologue() override;
        void EvacuateEpilogue() override;
        void Evacuate() override;
        void EvacuatePagesInParallel() override;
        void UpdatePointersAfterEvacuation() override;

        UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk, Address start,
            Address end) override;
        UpdatingItem* CreateRememberedSetUpdatingItem(
            MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) override;

        int CollectNewSpaceArrayBufferTrackerItems(ItemParallelJob* job);

        int NumberOfParallelMarkingTasks(int pages);

        MarkingWorklist* worklist_;

        YoungGenerationMarkingVisitor* main_marking_visitor_;
        base::Semaphore page_parallel_job_semaphore_;
        std::vector<Page*> new_space_evacuation_pages_;
        std::vector<Page*> sweep_to_iterate_pages_;

        MarkingState marking_state_;
        NonAtomicMarkingState non_atomic_marking_state_;

        friend class YoungGenerationMarkingTask;
        friend class YoungGenerationMarkingVisitor;
    };

#endif // ENABLE_MINOR_MC

} // namespace internal
} // namespace v8

#endif // V8_HEAP_MARK_COMPACT_H_
